package 算法.LeetCode91.每日打卡题目;

import 算法.NiuKe.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: 谢君臣
 * @create: 2021-02-15 14:07
 * @founction: XXXX
 */
public class day14 {
    public static void main(String[] args) {

    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        List<Integer> pre1 = new ArrayList<>();
        List<Integer> pre2 = new ArrayList<>();
        pre1 = getMid(p,pre1);
        pre2 = getMid(q,pre2);
        if (pre1.equals(pre2))
            if (pre1.size()>0)
                return getMid(p.right,new ArrayList<>()).equals(getMid(q.right,new ArrayList<>()));
            else
                return true;
        else
            return false;
    }

    public List<Integer> getMid(TreeNode root, List<Integer> list) {
        if (root==null)
            return new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node!=null){
            stack.push(node);
            node = node.left;
        }
        while (!stack.empty()){
            TreeNode n = stack.pop();
            list.add(n.val);
            if (n.right!=null){
                node = n.right;
                while (node!=null){
                    stack.push(node);
                    node = node.left;
                }
            }
        }
        return list;
    }
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        List<Integer> pre1 = new ArrayList<>();
        List<Integer> pre2 = new ArrayList<>();
        pre1 = getPre(p,pre1);
        pre2 = getPre(q,pre2);
        return pre1.equals(pre2);
    }

    public List<Integer> getPre(TreeNode root, List<Integer> list) {
        if (root!=null){
            list.add(root.val);
            list = getPre(root.left,list);
            list = getPre(root.right,list);
        }
        return list;
    }
}
